题解 P5146@洛谷 【最大差值】

C++语言题解

P党再见

看见标签:DP,想DP我不会这样发不了题解,于是有以下思路

思路:最大差值……差值!(划重点)差值怎么办呢?当然是用差分了!

懂了的退出自己想想。

差分,具体怎么办呢?最大差值,即找出差分数组的最大子段和。特别地,这里差分数组第一个位置要置成非正数(因为不能取第一个数前面隐藏的0),否则样例会过不了。

样例解释

类型 0 1 2 3 4 5 6 7 8 9
原数组 1 3 4 6 7 9 10 1 2 9
差分 -1000000 2 1 2 1 2 1 -9 1 7
最大子段和 * * * * * *

最大子段和为d[1]+d[2]+d[3]+d[4]+d[5]+d[6],换回原数组即为a[1]-a[0]+a[2]-a[1]+a[3]-a[2]+a[4]-a[3]+a[5]-a[4]+a[6]-a[5],即a[6]-a[0],为最大差值。

代码:

#include <iostream>
#include <limits.h>
using namespace std;

int n, a[1000001], d[1000001], f[1000001];

int maxsum(void)
{
    f[0] = d[0];
    for(int i=1;i<n;i++) f[i] = max(f[i-1] + d[i], d[i]);
    int m = INT_MIN;
    for(int i=0;i<n;i++) m = max(m, f[i]);
    return m;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
	{
		cin>>a[i];
		d[i] = i ? (a[i] - a[i-1]) : -1000000;//差分 
	}
//	for(int i=0;i<n;i++) cout<<d[i]<<" ";
//	cout<<endl;
    cout<<maxsum()<<endl;
    return 0;
}